#include "string_array.h"
#include <algorithm>

using namespace std;

myStr::myStr(const char* str){
    int size = 0;
    for(int y = 0; str[y] != '\0'; y ++){
        size ++;
    }
    data = new char[size];
    for(int y = 0; y < size; y ++){
        data[y] = str[y];
    }
    length = size;
    next = NULL;
    nextVal = NULL;
}
myStr::myStr(){
    length = 0;
    data = NULL;
    next = NULL;
    nextVal = NULL;
}

myStr::~myStr() = default;

void myStr::kmp_next(){
    next = new int[length];
    int i = 0;
    int j = -1;
    next[0] = 0;
    while(i < length){
        if(j == -1 || data[i] == data[j]){
            i ++;
            j ++;
            next[i] = j + 1;
        }
        else{
            j = next[j] - 1;
        }
    }
}

int myStr::comparenext(int a){
    if(a == 0){
        return 0;
    }
    if(data[next[a] - 1] != data[a]){
        return next[a];
    }
    else{
        comparenext(next[a] - 1);
        }
}

void myStr::kmp_nextVal(){
    nextVal = new int[length];
    nextVal[0] = 0;
    for(int i = 1; i < length; i ++){
        nextVal[i] = comparenext(i);
    }
}

bool replaceStr(myStr& str, const int& index, const myStr& t, const myStr& v){    
    int i = 0, j = 0; 
    for(i = index - 1; i < str.length; i ++){
        if(str.data[i] == t.data[j]){
            j ++;
        }
        else{
            j = 0;
            i = i - j;
            }
        if(j == t.length){
            break;
        }
    }
    if(j != t.length){
        return 0;
    }
    i = i - t.length;
    char* tem = new char[str.length + v.length - t.length];
    for(int o = 0; o <= i; o ++){
        tem[o] = str.data[o];
    }
    for(int o = 0; o < v.length; o ++){
        tem[i + 1 + o] = v.data[o];
    }
    for(int o = 1; o + t.length + i < str.length; o ++){
        tem[i + v.length + o] = str.data[i + t.length + o];
    }
    delete str.data;
    str.data = tem;
    str.length = str.length + v.length - t.length;
    return 1;
}

int simpleMatch(const myStr& str, const myStr& match){
    int i = 0, j = 0;
    while(i < str.length){
        if(str.data[i] == match.data[j]){
            i ++;
            j ++;
        }
        else{
            i = i - j + 1;
            j = 0;
        }
        if(j == match.length){
            return i - j + 1;
        }
    }
    return -1;
}

int kmpMatch(const myStr& str, const myStr& match){
    int i = 0, j = 0;
    while(i < str.length && j < match.length){
        if(str.data[i] == match.data[j] || j == -1){
            i ++;
            j ++;
            
        }
        else{
            j = match.next[j] - 1;
        }
        if(j == match.length){
            return i - j + 1;
        }
    }
    return -1;
}

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;
    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

bool compare(const matrixNode & a,  const matrixNode & b){
    return(a.row < b.row || (a.row == b.row && a.col < b.col));
}

myMatrix::myMatrix(const int& rnum, const int& cnum, const int& num, const int* data){
    nodeList = new matrixNode[num];
    rowNum = rnum;
    colNum = cnum;
    nodeNum = num;
    matrixNode x;
    for(int i = 0; i < num; i ++){
        nodeList[i].row = data[3 * i];
        nodeList[i].col = data[3 * i + 1];
        nodeList[i].value = data[3 * i + 2];
        // x.row = data[3 * i];
        // x.col = data[3 * i + 1];
        // x.value = data[3 * i + 2];
        // for(int j = 0; j < i; j ++){
        //     if(x.row < nodeList[j].row || (x.row == nodeList[j].row && x.col < nodeList[j].col)){
                
        //         nodeList[i].row = nodeList[j].row;
        //         nodeList[i].col = nodeList[j].col;
        //         nodeList[i].value = nodeList[j].value;
        //     }
        // }
    }
    sort(nodeList, nodeList + nodeNum, compare);
}

myMatrix::~myMatrix(){
    delete []nodeList;
    nodeList = NULL;
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
}

myMatrix::myMatrix(){
    nodeList = NULL;
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
}

void myMatrix::FastTransposeSMatrix(myMatrix& T){
    T.nodeNum = nodeNum;
    T.colNum = rowNum;
    T.rowNum = colNum;
    T.nodeList = new matrixNode[nodeNum];
    int *num = new int[colNum];
    int *copt = new int[colNum];
    for(int i = 0; i < colNum; i ++){
        num[i] = 0;
        copt[i] = 0;
    }
    copt[0] = 0;
    for(int i = 0; i < nodeNum; i ++){
        num[nodeList[i].col] ++;
    }
    for(int i = 1; i < colNum; i ++){
        copt[i] = copt[i-1] + num[i-1];
    }
    // for(int y = 0; y < nodeNum; y ++){
    //     T.nodeList[y].value = nodeList[y].value;
    //     T.nodeList[y].col = nodeList[y].row;
    //     T.nodeList[y].row = nodeList[y].col;
    // }
    int col = 0, q = 0;
    for(int y = 0; y < nodeNum; y ++){
        col = nodeList[y].col;
        q = copt[col];
        T.nodeList[q].value = nodeList[y].value;
        T.nodeList[q].col = nodeList[y].row;
        T.nodeList[q].row = nodeList[y].col;
        copt[col] ++;
    }
};